package org.example;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Test1 {
    //leetcode 513 找树左下角的值 https://leetcode.cn/problems/find-bottom-left-tree-value/description/
    /**
     * 方法一：层序遍历
     * @param root
     * @return
     */
    public int findBottomLeftValue1(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        List<Integer> list = null;
        while (!deque.isEmpty()) {
            int count = deque.size();
            list  = new ArrayList<>();
            while (count > 0) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if (node.left != null) deque.add(node.left);
                if (node.right != null) deque.add(node.right);
                count--;
            }
        }
        return list.get(0);
    }

    /**
     * 方法二：dfs
     */
    int maxLength = -1, result;
    public int findBottomLeftValue(TreeNode root) {
        traversal(root,0);
        return result;
    }

    public void traversal(TreeNode root, int depth) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            //只有当depth第一次大于maxLength的时候，才会更新result的值，这样就保证了最后一层的第一个结点的值
            if (depth > maxLength) {
                maxLength = depth;
                result = root.val;
            }
        }
        if (root.left != null) traversal(root.left, depth + 1);
        if (root.right != null) traversal(root.right,depth + 1);
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        b.left = a;
        b.right = c;
        test1.findBottomLeftValue(b);
        System.out.println(444);
    }
}
